package src.src;

/**
 * 
 * @author paulo
 */
public class quickSort {

    private static Comparable[] data;

    /**
     * 
     * @param list
     * @param n
     */
    public static void quickSort_srt(Comparable[] list, int n) // post: the values in data[0..n-1] are in ascending order
    {
        quickSortRecursive(list, 0, n - 1);
        setData(list);
    }

    private static void quickSortRecursive(Comparable[] data, int left, int right) // pre: left <= right
    // post: data[left..right] in ascending order
    {
        int pivot; // the final location of the leftmost value
        if (left >= right) {
            return;
        }
        pivot = partition(data, left, right); /* 1 - place pivot */
        quickSortRecursive(data, left, pivot - 1); /* 2 - sort small */
        quickSortRecursive(data, pivot + 1, right);/* 3 - sort large */
        /* done! */
    }

    /**
     * 
     * @param data
     * @param index1
     * @param index2
     * @return
     */
    public static Comparable[] swap(Comparable[] data, int index1, int index2) {
        Comparable temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
        return data;
    }

    private static int partition(Comparable[] data, int left, int right) // pre: left <= right
    // post: data[left] placed in the correct (returned) location
    {
        while (true) {
            // move right "pointer" toward left
            while (left < right && data[left].compareTo(data[right]) < 0) {
                right--;
            }
            if (left < right) {
                swap(data, left++, right);
            } else {
                return left;
            }
            // move left pointer toward right
            while (left < right && data[left].compareTo(data[right]) < 0) {
                left++;
            }
            if (left < right) {
                swap(data, left, right--);
            } else {
                return right;
            }
        }
    }

    /**
     * 
     * @return
     */
    public static Comparable[] getData() {
        return data;
    }

    /**
     * 
     * @param data
     */
    public static void setData(Comparable[] data) {
        quickSort.data = data;
    }
}
